/*	Program P12-7 Breadth-first traversal.
	
    Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	Copyright 1998. All Rights Reserved
*/

/*	==================== breadthFirst ==================== 
	Process the data of the graph in breadth-first order. 
	   Pre  graph is a pointer of a graph head structure
	   Post graph has been processed
*/

template <class TYPE, class KTYPE> 
void Graph<TYPE, KTYPE> ::  breadthFirst 
               (void(*process) (TYPE dataProc))
{
//	Local Definitions 
	bool           success;
	Vertex<TYPE>  *walkPtr;
	Vertex<TYPE>  *vertexPtr;
	Vertex<TYPE>  *vertToPtr;
	Arc<TYPE>     *arcWalkPtr;

	Queue<Vertex<TYPE>*> queue;
	
// 	Statements 
	if (!first)
	    return;
 
	// Set processed flags to not processed 
	walkPtr = first;
	while (walkPtr)
	   {
	    walkPtr->processed = 0;
	    walkPtr            = walkPtr->pNextVertex;
	   } // while 
	
	// Process each vertex in list 
	walkPtr = first;
	while (walkPtr)
	   {
	    if (walkPtr->processed < 2)
	       {
	        if (walkPtr->processed < 1)
	           {
	            // Enqueue and set flag to queue 
	            success = queue.enqueue(walkPtr);
	            if (!success)
	              cout << "\aQueue overflow 100\a\n",
	               exit (100);
	            walkPtr->processed = 1;
	           } // if processed < 1 
	       } // if processed < 2 

	    // Process descendents of vertex at queue front 
	    while (!queue.emptyQueue ())
	       {
	        queue.dequeue(vertexPtr);
	        process (vertexPtr->data);
	        vertexPtr->processed = 2;
	        
	        // Enqueue all vertices from adjacency list 
	        arcWalkPtr = vertexPtr->pArc;
	        while (arcWalkPtr)
	           {
	            vertToPtr = arcWalkPtr->destination;
	            if (vertToPtr->processed == 0)
	               {
	                success = queue.enqueue(vertToPtr);
	                if (!success)
	                   cout << "\aQueue overflow 101\a\n",
	                   exit (101);
	                vertToPtr->processed = 1;
	               } // if vertToPtr 
	            arcWalkPtr = arcWalkPtr->pNextArc;
	           } // while arcWalkPtr 
	           
	       } // while !emptyQueue 
	    walkPtr = walkPtr->pNextVertex;
	   } // while walkPtr 
	return;
 } // breadthFirst 
